﻿using System.Collections.Generic;
using System.Linq;
using Gumini.JulaDB.Expressions;
using Gumini.JulaDB.Expressions.Operators;
using Gumini.JulaDB.Planner;
using System.Diagnostics;

namespace Gumini.JulaDB.Optimizer
{
    using TableMapping = Dictionary<string, TableNode>;

    /// <summary>
    /// TODO: Update summary.
    /// </summary>
    internal class QueryOptimizer
    {
        public QueryPlan BuildOptimizedPlan(QueryPlan sourcePlan)
        {
            Debug.WriteLine("==== initial query plan ====");
            Debug.WriteLine(sourcePlan.ToString());

            var expressions = SplitWhereExpression(sourcePlan);
            var sourceTables = GetSourceTables(sourcePlan);
            var tableMapping = BuildNameToTableMapping(sourceTables);

            var joinExpressions = GetJoinExpressions(expressions, tableMapping);
            var joinClauses = BuildJoinClauses(joinExpressions, tableMapping);
            joinClauses = NormalizeJoinClauses(sourceTables, joinClauses);
            joinClauses = GroupJoinClauses(joinClauses);

            List<InnerJoinClause> unusedJoinClauses;
            var optimizedSubtree = BuildJoinSubtree(sourceTables, joinClauses, out unusedJoinClauses);

            var remainingExpressions =
                GetNonJoinExpressions(expressions, tableMapping).Union(
                unusedJoinClauses.Select(c => c.GetEquivalentExpression()));

            if (remainingExpressions.Any())
            {
                var newWhereCondition = BuildConjunctionOfExpressions(remainingExpressions);
                optimizedSubtree = new FilterNode(optimizedSubtree, newWhereCondition);
            }

            var optimizedFullTree = RebuildPlanTree(sourcePlan.RootNode, optimizedSubtree);
            var optimizedPlan = new QueryPlan(optimizedFullTree);

            Debug.WriteLine("==== optimized query plan ====");
            Debug.WriteLine(optimizedPlan.ToString());

            return optimizedPlan;
        }

        private static PlanNode RebuildPlanTree(PlanNode sourceNode, PlanNode optimizedSubtree)
        {
            if (sourceNode is FilterNode ||
                sourceNode is JoinNode ||
                sourceNode is TableNode)
                return optimizedSubtree;
            else
            {
                var unarySourceNode = (UnaryPlanNode)sourceNode;
                var newSubNode = RebuildPlanTree(unarySourceNode.Child, optimizedSubtree);
                unarySourceNode.Child = newSubNode;
                return unarySourceNode;
            }
        }

        private static PlanNode BuildJoinSubtree(List<TableNode> allTableNodes, List<InnerJoinClause> joinClauses, out List<InnerJoinClause> unusedClauses)
        {
            var remainingClauses = new Queue<InnerJoinClause>(joinClauses);
            var unusedNodes = new HashSet<PlanNode>(allTableNodes);
            var planTreeFragments = new List<PlanNode>();

            unusedClauses = new List<InnerJoinClause>();

            while (remainingClauses.Count > 0)
            {
                var currentClause = remainingClauses.Dequeue();
                if (unusedNodes.Contains(currentClause.LeftNode) && unusedNodes.Contains(currentClause.RightNode))
                {
                    // creating a new subtree joining the two tables
                    var newFragment = new InnerJoinNode(currentClause);
                    planTreeFragments.Add(newFragment);

                    unusedNodes.Remove(currentClause.LeftNode);
                    unusedNodes.Remove(currentClause.RightNode);
                }
                else if (!unusedNodes.Contains(currentClause.LeftNode) && !unusedNodes.Contains(currentClause.RightNode))
                {
                    // there is a cyclic dependency, we will not use this clause for inner join
                    unusedClauses.Add(currentClause);
                }
                else // exactly one of the tables was already used in join
                {
                    var existingFragment = planTreeFragments.
                        Where(f => f.ContainsNode(currentClause.LeftNode) || f.ContainsNode(currentClause.RightNode)).
                        Single();

                    if (existingFragment.ContainsNode(currentClause.RightNode))
                        currentClause = currentClause.GetReversedClause();

                    var nodeToAttach = currentClause.RightNode;

                    planTreeFragments.Remove(existingFragment);
                    unusedNodes.Remove(nodeToAttach);

                    var newFragment = new InnerJoinNode(
                        nodeA: existingFragment,
                        nodeB: nodeToAttach,
                        columnPairs: currentClause.ColumnPairs);

                    planTreeFragments.Add(newFragment);
                }
            }

            planTreeFragments.AddRange(unusedNodes);
            var result = planTreeFragments.First();
            foreach (var fragment in planTreeFragments.Skip(1))
                result = new CrossJoinNode(result, fragment);

            return result;
        }

        private static List<InnerJoinClause> GroupJoinClauses(List<InnerJoinClause> clauses)
        {
            return clauses.
                GroupBy(c => new { LeftTable = c.LeftNode, RightTable = c.RightNode }).
                Select(g =>
                    new InnerJoinClause(
                        left: g.Key.LeftTable,
                        right: g.Key.RightTable,
                        columnPairs: g.SelectMany(c => c.ColumnPairs))).
                ToList();
        }

        private static List<InnerJoinClause> NormalizeJoinClauses(List<TableNode> tables, List<InnerJoinClause> sourceJoinClauses)
        {
            var result = new List<InnerJoinClause>();
            foreach (var clause in sourceJoinClauses)
            {
                if (tables.IndexOf((TableNode)clause.LeftNode) > tables.IndexOf((TableNode)clause.RightNode))
                    result.Add(clause.GetReversedClause());
                else
                    result.Add(clause);
            }
            return result;
        }

        private static List<InnerJoinClause> BuildJoinClauses(List<BinaryExpression> joinExpressions, TableMapping mapping)
        {
            var result = new List<InnerJoinClause>();
            foreach (var expr in joinExpressions)
            {
                var leftVariable = expr.Left as Variable;
                var rightVariable = expr.Right as Variable;

                var leftTable = mapping[leftVariable.TableName];
                var rightTable = mapping[rightVariable.TableName];
                var columnPair = new ColumnPair(leftVariable, rightVariable);

                var clause = new InnerJoinClause(
                    left: leftTable,
                    right: rightTable,
                    columnPair: columnPair);

                result.Add(clause);
            }
            return result;
        }

        private static TableMapping BuildNameToTableMapping(IEnumerable<TableNode> tableNodes)
        {
            var result = new Dictionary<string, TableNode>();
            foreach (var table in tableNodes)
                foreach (var name in table.TableNames)
                    result.Add(name, table);
            return result;
        }

        /// <summary>
        /// Join expressions are in the following form:
        /// table1.columnA = table2.columnB
        /// </summary>
        private static bool IsJoinExpression(Expression expr, TableMapping mapping)
        {
            var binaryExpr = expr as BinaryExpression;
            if (binaryExpr == null)
                return false;
            
            if (!(binaryExpr.Operator is EqualOperator))
                return false;
            
            var variableA = binaryExpr.Left as Variable;
            var variableB = binaryExpr.Right as Variable;
            if (variableA == null || variableB == null)
                return false;

            // checking if the condition is for different tables
            var tableA = mapping[variableA.TableName];
            var tableB = mapping[variableB.TableName];
            return tableA != tableB;
        }

        private static List<BinaryExpression> GetJoinExpressions(IEnumerable<Expression> allExpressions, TableMapping mapping)
        {
            return allExpressions.Where(ex => IsJoinExpression(ex, mapping)).
                Cast<BinaryExpression>().ToList();
        }

        private static List<Expression> GetNonJoinExpressions(IEnumerable<Expression> allExpressions, TableMapping mapping)
        {
            return allExpressions.Where(ex => !IsJoinExpression(ex, mapping)).
                ToList();
        }

        private static Expression BuildConjunctionOfExpressions(IEnumerable<Expression> expressions)
        {
            if (expressions.Count() == 1)
                return expressions.Single();
            else
                return new BinaryExpression("AND",
                    left: expressions.First(),
                    right: BuildConjunctionOfExpressions(expressions.Skip(1)));
        }

        /// <summary>
        /// Splits the expression into subexpressions separated by 'AND'.
        /// </summary>
        private static List<Expression> SplitWhereExpression(QueryPlan sourcePlan)
        {
            // there should be 0 or 1 element of type FilterNode
            var filterNode = sourcePlan.RootNode.GetNodesByType<FilterNode>().SingleOrDefault();

            if (filterNode == null)
                return new List<Expression>();

            return GetConjunctionOfExpressions(filterNode.Expression).ToList();
        }

        private static IEnumerable<Expression> GetConjunctionOfExpressions(Expression expression)
        {
            var binaryExpression = expression as BinaryExpression;
            if (binaryExpression == null)
                return new[] { expression };

            var andOperator = binaryExpression.Operator as AndOperator;
            if (andOperator == null)
                return new[] { expression };

            return
                GetConjunctionOfExpressions(binaryExpression.Left).Union(
                GetConjunctionOfExpressions(binaryExpression.Right));
        }

        private static List<TableNode> GetSourceTables(QueryPlan sourcePlan) 
        {
            return sourcePlan.RootNode.GetNodesByType<TableNode>().ToList();
        }
    }
}
